#define _CRT_SECURE_NO_WARNINGS 1


////前序遍历
//void PreOder(struct TreeNode* root, int* a, int* i)
//{
//    if (root == NULL)
//        return;
//    //形参不影响实参，所有用指针简引用改变i
//    a[(*i)++] = root->val;
//    PreOder(root->left, a, i);
//    PreOder(root->right, a, i);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    //returnSize为数组大小，决定遍历次数
//    int n = TreeSize(root);
//    int* a = (int*)malloc(sizeof(int) * n);
//    int i = 0;
//    PreOder(root, a, &i);
//    *returnSize = n;
//    return a;
//}

//中序遍历
// int TreeSize(struct TreeNode* root)
//{
//return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//void InOrder(struct TreeNode* root, int* a, int* i)
//{
//    if (root == NULL)
//        return;
//    InOrder(root->left, a, i);
//    a[(*i)++] = root->val;
//    InOrder(root->right, a, i);
//}
//
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    int n = TreeSize(root);
//    int* a = (int*)malloc(sizeof(int) * n);
//    int i = 0;
//    InOrder(root, a, &i);
//    *returnSize = n;
//    return a;
//}


//后序遍历
// int TreeSize(struct TreeNode* root)
//{
//    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//
//void PostOrder(struct TreeNode* root, int* a, int* i)
//{
//    if (root == NULL)
//        return;
//    PostOrder(root->left, a, i);
//    PostOrder(root->right, a, i);
//    a[(*i)++] = root->val;
//}
//int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//    int n = TreeSize(root);
//    int* a = (int*)malloc(sizeof(int) * n);
//    int i = 0;
//    PostOrder(root, a, &i);
//    *returnSize = n;
//    return a;
//}